package com.practice.niuke.new_direct_practice.class13;

/**
 * 给定一个二维数组matrix，可以从任何位置出发，每一步可以走向上、下、左、右，四
 * 个方向。返回最大递增链的长度。
 * 例子：
 * matrix =
 * 5 4 3
 * 3 1 2
 * 2 1 3
 * 从最中心的1出发，是可以走出1 2 3 4 5的链的，而且这是最长的递增链。所以返回长
 * 度5
 */
public class Code02_LongestIncreasingPath {

    /**
     * 暴力递归法
     *
     * @param matrix matrix二维数组
     * @return int
     */
    public static int maxPath(int[][] matrix) {
        int ans = Integer.MIN_VALUE;
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                ans = Math.max(ans, process(matrix, row, col));
            }
        }
        return ans;
    }

    /**
     * 暴力递归法的递归函数：
     * 假设在matrix中，从i行，j列出发，能走出的最长递增路径，返回
     *
     * @param matrix matrix二维数组
     * @param i      从i行，j列出发
     * @param j      从i行，j列出发
     * @return 能走出的最长递增路径的长度
     */
    public static int process(int[][] matrix, int i, int j) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
            // i, j位置越界，直接返回-1
            return -1;
        }
        int next1 = 0; // 上
        int next2 = 0; // 下
        int next3 = 0; // 左
        int next4 = 0; // 右
        if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
            // i-1 >= 0 说明有上面的位置，并且上面的位置的值大于我当前的值（matrix[i-1][j] > matrix[i][j]）
            // 可以往上走
            next1 = process(matrix, i - 1, j);
        }
        if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
            // i+1 < matrix.length 说明有下面的位置，并且下面位置的值大于我当前的值（matrix[i+1][j] > matrix[i][j]）
            // 可以往下走
            next2 = process(matrix, i + 1, j);
        }
        if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
            // j-1 >= 0 说明有左面的位置，且左面位置的值大于我当前的值（matrix[i][j-1] > matrix[i][j]）
            // 可以往左走
            next3 = process(matrix, i, j - 1);
        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
            // j+1 < matrix[0].length 说明有右面的位置，且右面位置的值大于我当前位置的值
            // 可以往右走
            next4 = process(matrix, i - 1, j);
        }
        // 上下左右走出的最大值+我自己 == 走出的最大递增链的长度
        return 1 + Math.max(Math.max(next1, next2), Math.max(next3, next4));
    }


    /**
     * 由暴力递归到记忆化搜索（傻缓存方法）
     *
     * @param matrix matrix二维数组
     * @return int
     */
    public static int maxPath2(int[][] matrix) {
        int ans = Integer.MIN_VALUE;

        int[][] dp = new int[matrix.length][matrix[0].length];

        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                ans = Math.max(ans, process(matrix, row, col, dp));
            }
        }
        return ans;
    }


    /**
     * 由暴力递归到记忆化搜索（傻缓存方法）：
     * 假设在matrix中，从i行，j列出发，能走出的最长递增路径，返回
     *
     * @param matrix matrix二维数组
     * @param i      从i行，j列出发
     * @param j      从i行，j列出发
     * @param dp     傻缓存
     * @return 能走出的最长递增路径的长度
     */
    public static int process(int[][] matrix, int i, int j, int[][] dp) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
            return -1;
        }
        // 缓存中是否有值
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int next1 = 0;
        int next2 = 0;
        int next3 = 0;
        int next4 = 0;
        if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
            next1 = process(matrix, i - 1, j);
        }
        if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
            next2 = process(matrix, i + 1, j);
        }
        if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
            next3 = process(matrix, i, j - 1);
        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
            next4 = process(matrix, i - 1, j);
        }

        int ans = 1 + Math.max(Math.max(next1, next2), Math.max(next3, next4));
        // 将结果存入缓存
        dp[i][j] = ans;
        return ans;
    }


    public static int longestIncreasingPath(int[][] m) {
        if (m == null || m.length == 0 || m[0].length == 0) {
            return 0;
        }
        int[][] dp = new int[m.length][m[0].length];
        // dp[i][j]  (i,j)出发，走出的最长链长度
        int max = 0;
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[0].length; j++) {
                // 每一个(i,j)位置出发，都尝试
                max = Math.max(max, maxIncrease(m, dp, i + 1, j, m[i][j]) + 1);
                max = Math.max(max, maxIncrease(m, dp, i, j + 1, m[i][j]) + 1);
                max = Math.max(max, maxIncrease(m, dp, i - 1, j, m[i][j]) + 1);
                max = Math.max(max, maxIncrease(m, dp, i, j - 1, m[i][j]) + 1);
            }

        }
        return max;
    }

    // 来到的当前位置是i,j位置
    // p 上一步值是什么
    // 从(i,j)位置出发，走出的最长链，要求：上一步是可以迈到当前步上的
    public static int maxIncrease(int[][] m, int[][] dp, int i, int j, int p) {
        if (i < 0 || i >= m.length || j < 0 || j >= m[0].length || m[i][j] <= p) {
            return 0;
        }
        if (dp[i][j] == 0) { // i,j 出发，当前没算过
            dp[i][j] = maxIncrease(m, dp, i + 1, j, m[i][j]) + 1;
            dp[i][j] = Math.max(dp[i][j], maxIncrease(m, dp, i, j + 1, m[i][j]) + 1);
            dp[i][j] = Math.max(dp[i][j], maxIncrease(m, dp, i - 1, j, m[i][j]) + 1);
            dp[i][j] = Math.max(dp[i][j], maxIncrease(m, dp, i, j - 1, m[i][j]) + 1);
        }
        return dp[i][j];
    }

}
